package Algorithm.greedyAlgorithm;

import java.util.Arrays;

/**
 * 下一个更大的数字 https://www.codewars.com/kata/55983863da40caa2c900004e/train/java
 * 题目简述：给定一个正整数n，返回由n中每位数字重新排列构成的比n大且最接近n的数，不存在则返回-1。如15973下一个更大的数为17359
 */
public class NextBiggerNumber {

    /**
     * 思路：从右向左找出第一对相邻逆序的数字arr[i] arr[i+1]，若不存在相邻逆序，则已经是最大数字了，返回-1。
     * 然后再从右向i遍历找出比arr[i]大的最小数字和arr[i]进行交换，最后将[i+1, n)重排序
     */
    public static long nextBiggerNumber(long n) {
        char[] arr = String.valueOf(n).toCharArray();
        int i;
        for (i = arr.length-2;i >= 0;i--) { //从右向左找出第一对相邻逆序
            if (arr[i] < arr[i+1])
                break;
        }
        if (i == -1) return -1; //若不存在相邻逆序，返回-1
        //从右向i遍历找出比arr[i]大的最小数字和arr[i]进行交换
        int j = arr.length-1;
        while (arr[j] <= arr[i]) j--; // 此时[i+1, n)必然是从大到小有序的，所以可如此找
        char t = arr[i];arr[i] = arr[j];arr[j] = t;

        Arrays.sort(arr, i+1, arr.length); //将[i+1, n)重排序
        try {
            return Long.parseLong(new String(arr));
        } catch (NumberFormatException e) {
            return -1;
        }
    }

    public static void main(String[] args) {
        System.out.println(nextBiggerNumber(9223372036854775807L));
        System.out.println(nextBiggerNumber(15973));
    }
}
